package site.wanjiahao.list;

import java.util.Iterator;

// 优化ArrayList, 存在一个指针指向首元素
public class ArrayListOptimize<E> extends AbstractList<E> implements Iterable<E> {

    private Object[] elements;

    // 指向首元素的指针
    private int first;

    public ArrayListOptimize() {
        this(DEFAULT_CAPACITY);
    }

    public ArrayListOptimize(int capacity) {
        if (capacity <= DEFAULT_CAPACITY) {
            capacity = DEFAULT_CAPACITY;
        }
        elements = new Object[capacity];
    }

    @Override
    public void add(E ele) {
        // 添加元素至线性表头部
        add(size, ele);
    }

    @Override
    public E get(int index) {
        rangeCheck(index);
        return (E) elements[mapToIndex(index)];
    }

    @Override
    public E set(int index, E ele) {
        rangeCheck(index);
        E old = (E) elements[mapToIndex(index)];
        elements[mapToIndex(index)] = ele;
        return old;
    }

    /*
     *  最好:  O(1) 在动态数组最后面添加
     *  最坏   O(n) 在动态数组起始位置添加
     *  平均复杂度  O(n)
     * */
    @Override
    public void add(int index, E ele) {
        // 判断添加索引是否合法
        rangeCheckForAdd(index);
        // 确保线性表容量足够
        ensureCapacity();
        if (index == size) {
            elements[mapToIndex(index)] = ele;
        } else {
            // 动态数组中部添加
            // 移动元素，判断添加索引是否在左半部分，还是右半部分
            int end = (size - 1) >> 1;
            if (index > end) {
                // 右半部分
                if (size - index > 0)
                    System.arraycopy(elements, mapToIndex(index), elements, mapToIndex(index + 1), size - index);
                elements[mapToIndex(index)] = ele;
            } else {
                if (index == 0) {
                    // 首部位置添加
                    elements[mapToIndex(-1)] = ele;
                    first = mapToIndex(-1);
                } else {
                    if (index > 0)
                        // 左半部分
                        System.arraycopy(elements, mapToIndex(0), elements, mapToIndex(-1), index);
                    first = mapToIndex(-1);
                    elements[mapToIndex(index)] = ele;
                }
            }
        }

        size++;
    }

    @Override
    public E remove(int index) {
        rangeCheck(index);
        int end = (size - 1) >> 1;
        E old = get(index);
        if (index == size - 1) {
            // 尾部删除
            elements[mapToIndex(index)] = null;
            if (size == 1) {
                first = 0;
            }
        } else {
            // 中部删除
            if (index > end) {
                // 右半部分
                if (size - index - 1 > 0)
                    System.arraycopy(elements, mapToIndex(index + 1), elements, mapToIndex(index), size - index - 1);
                // 最后元素至空
                elements[mapToIndex(size - 1)] = null;
            } else {
                // 左半部分
                if (index > 0)
                    System.arraycopy(elements, mapToIndex(0), elements, mapToIndex(1), index);
                // 第一个元素至空
                elements[mapToIndex(0)] = null;
                first = mapToIndex(1);
            }
        }
        size--;
        // 缩容操作
        trim();
        return old;
    }

    // 当前剩余容量大于总容量一半，进行缩容操作
    private void trim() {
        int oldCapacity = elements.length;
        int newCapacity = oldCapacity >> 1;

        if (size > newCapacity || size <= DEFAULT_CAPACITY) return;

        // 缩容
        Object[] newAry = new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newAry[i] = elements[mapToIndex(i)];
        }
        elements = newAry;
        first = 0;
    }

    @Override
    public int indexOf(E ele) {
        // 使用equals方法比较，比较判断条件扩展性高，而不是直接比较内存地址
        if (ele != null) {
            for (int i = 0; i < size; i++) {
                if (ele.equals(elements[mapToIndex(i)])) {
                    return i;
                }
            }
        } else {
            for (int i = 0; i < size; i++) {
                if (null == elements[mapToIndex(i)]) {
                    return i;
                }
            }
        }
        return NOT_FOUND_ELEMENT;
    }

    @Override
    public void clear() {
        for (int i = 0; i < size; i++) {
            // 释放内存数据
            elements[mapToIndex(i)] = null;
        }
        size = 0;
    }

    @Override
    public String toString() {
        int end = elements.length - 1;
        StringBuilder sb = new StringBuilder();
        sb.append("size: ")
                .append(size)
                .append(", fist: ")
                .append(first).append(", elements: ");
        sb.append("[");
        for (int i = 0; i < elements.length; i++) {
            sb.append(elements[i]);
            if (i != end) {
                sb.append(", ");
            }
        }
        sb.append("]");
        return sb.toString();
    }

    @Override
    public Iterator<E> iterator() {
        return new DefaultIter();
    }

    // 映射循环索引
    private int mapToIndex(int index) {
        index = first + index;
        if (index < 0) {
            index = index + elements.length;
        } else {
            // 取模运算优化
            index = index - ((index >= elements.length)? elements.length: 0);
//            index = index % elements.length;
        }
        return index;
    }


    private void ensureCapacity() {
        int capacity = size + 1;
        int oldCapacity = elements.length;
        // 判断容量是否足够
        if (capacity >= oldCapacity) {
            // 增加1.5倍容量
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            Object[] newAry = new Object[newCapacity];
            // 拷贝数组
            for (int i = 0; i < size; i++) {
                newAry[i] = elements[mapToIndex(i)];
            }
            elements = newAry;
            first = 0;
        }
    }

}
